The present invention relates to high level synthesis of integrated circuits and specifically to synthesis for testability and efficiency in hardware shared implementation of such circuits by partial scan techniques. Quite specifically, the invention concerns hardware sharing for minimizing the quantity of scan registers required to break loops in data paths in order to perform partial scan testing of integrated circuits.
High level synthesis encompasses a variety of synthesis tasks, such as partitioning, module selection, and transformations, each of which has the potential to influence a number of design parameters, e.g., area, speed, and power. However, only allocation, scheduling, and assignment are widely recognized as mandatory tasks in high level synthesis. Allocation is the step during which it is decided how many basic blocks of each type of hardware unit (e.g. adder) will be used in the design. Scheduling is the step during which the temporal location within an interval of available time for each operation is fixed. Assignment is the step which assigns instances of operations to hardware units in the design.
A great variety of scheduling, allocation, and assignment algorithms have been studied in the high level synthesis literature. Examples are found in the article by M. C. McFarland et al, entitled "The High-Level Synthesis of Digital Systems" in Proceedings of the IEEE, 78(2):301-317, 1990 and in the book by R. Walker et al, entitled "A Survey of High-Level Synthesis Systems , Kluwer Academic Publishers, Boston, Mass. 1991. While the underlying algorithmic techniques vary from very simple heuristics to involved formal techniques, the goal of almost all the algorithms has been optimization of speed under resource constraints or its dual. More recently, the list of targeted goals was enhanced to include fault tolerance and testability.
It is widely recognized that testability of a circuit is dependent upon the testing methodology selected. The high level synthesis for testability methods can be broadly classified into two groups--BIST-based (built-in-self-test) and ATPG-based (automatic test pattern generation). The BIST-based methods assume the presence of a pseudo-random pattern generator for test vector generation and a MISR (multiple-input signature register) or other signature analyzers for response compression. Almost all BIST approaches assume a full-scan design methodology since random testing is not well-suited for non-scan sequential circuits.
ATPG-based testing methods assume that the test patterns would be generated by deterministic automatic test pattern generators. These techniques do not routinely assume full-scan, however, for ease of sequential circuit test generation, some techniques assume the presence of partial scan. Testability improvement using register assignment and scheduling was reported by T. C. Lee et al in an article entitled "Behavioral Synthesis for Easy Testability in Data Path Allocation" in Proc. of the Int'l Conf. on Computer-Design 1992 and by T. C. Lee et al in an article entitled "Behavioral Synthesis for Easy Testability in Data Path Scheduling" in Proc. of the Int'l Conf. on Computer-Aided Design, pp. 616-619, 1992, respectively. In both cases, testability improvement was actually demonstrated by running a sequential test pattern generator, STEED from the University of California at Berkeley. Chen and Saab describe in an article entitled "Behavioral Synthesis for Testability" in Proc. of the Int'l Conf. on Computer-Aided Design", pp. 612-615, Nov. 1992 the use of a high-level testability analysis program to identify testable structures and synthesize them to improve testability. An approach to generate testable data paths, by minimizing the number of self-loops, was reported by A. Majumdar et al in an article entitled "Incorporating Testability Considerations in High-Level Synthesis" in the Proc. of the Int'l Sym of Fault-Tolerant Computing, 1992. However, the actual fault coverages were not reported. More recently. Lee et al developed a method to minimize formation of loops in the data path by partial scan and proper register assignment as described in an article entitled "Behavioral Synthesis of Highly Testible Data Paths Under the Non-Scan and Partial Scan Environments" in Proc. Design Automation Conf. pp. 292-297, 1993.
Several researchers have attempted to improve the testability of circuits by manipulating the R2 (register transfer)-level description. It has been shown that the use of RT-level information to select scan flip-flops results in significantly better performance when compared to techniques limited to gate-level information only. Also, transformation and optimization techniques have been proposed which utilize RT-level information to generate optimized designs that are 100% testable under full scan.
An object of the present invention is to synthesize designs which are easy-to-test by a gate-level sequential deterministic automatic test pattern generator. There are several factors which influence the testability of a sequential circuit. The dependencies of the flip-flops (FFs) of a sequential circuit is captured by an S-graph, where each node corresponds to a FF. There is a directed edge from node u to node v if there is a combinational path from FF u to FF v in the sequential circuit. It is known that sequential test generation complexity might grow exponentially with the length of the cycles in the S-graph. The sequential test generation complexity grows only linearly with the longest path (sequential depth) in the S-graph.
The scan flip-flops are selected so that the S-graph has no cycles except self-loops, and the sequential depth is minimal. A sequential circuit with no loops, other than self-loops, and having low sequential depth, is easily-testable by current deterministic sequential test pattern generators.
Most of the hard-to-detect faults in a sequential circuit are found in moderately sized and large-strongly connected components (SCCs). Cliques should be broken with high priority and hard-to-detect faults seldom occur in self-loops. As a result, there has been developed a highly efficient partial scan approach at the gate-level, which selects scan FFs using the knowledge of faults aborted by the test pattern generator.
In U.S. Pat. No. 5,043,986 issued in the names of Agrawal and Cheng, a method of partial scan design for chip testing is dscribed. Tim method involves establishing a subset of the memory elements of a circuit. The subset is chosen such that, while in a test mode, substantially all feedback paths equal to or greater than a selected cycle length in the circuits are eliminated. Preferably, the scan elements are selected to eliminate all cycles of a circuit. The patent describes the existence of loops at the gate level and the solution is a test design for gate level testing.
The present invention considers high level synthesis circuit design along with the testability of the circuit being designed. That is, all sources of loops created in the data path are identified. The present invention also describes a method which simultaneously schedules and assigns the operations in a manner for generating a design which has low hardware cost and low partial scan testing overhead cost. The hardware sharing is designed into the circuit at the time of high level synthesis in a manner to avoid the formation of loops. The invention considers all loops formed in the data path namely: CDFG (control data flow graph) loops which are produced in the data path irrespective of the scheduling and assignments as a consequence of the loops in the corresponding CDFG; assignment loops which are produced whenever two or more operations in the path of a CDFG are assigned to the same module; false loops which are produced when multiple operations in disjoint paths are assigned to the same modules under certain conditions; and register file cliques which are formed when multiple registers belonging to a module receive an input from the output of the same module. The operations are scheduled and assigned for avoiding the formation of loops in the data path, while preserving high resource utilization.